package leetcode.Leetcode239;

import java.util.Comparator;
import java.util.PriorityQueue;

class DraftSolution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        //优先队列里队头保持的永远是最大值
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                //二元组o1,o2保存的是新进入滑动窗口的值，第一个是值，第二个是位置，queue进入队列默认队尾是最小的值
                //值不相等，比较值，值相等比较Index,index大的在前面，其实第二个没什么区别，第一个保证是大顶堆。
                return o1[0]!=o2[0]?o2[0]-o1[0]:o2[1]-o1[1];
            }
        });
        for (int i = 0; i < k; ++i) {
            pq.offer(new int[]{nums[i], i});
        }
        int[] ans = new int[n - k + 1];
        ans[0] = pq.peek()[0];
        for (int i = k; i < n; ++i) {
            pq.offer(new int[]{nums[i], i});
            while (pq.peek()[1] <= i - k) {
                pq.poll();
            }
            ans[i - k + 1] = pq.peek()[0];
        }
        return ans;
    }
}